week9 HW 戴偉璿

$\text{1.}$

$(a)$

$P\rightarrow Q = P\rightarrow f_1(n)\rightarrow f_2(f_1(n))\rightarrow f_3(f_2(f_1(n)))$

複雜度為$O(f_1(n),f_2(n),f_3(n))=O(max(f_1(n),f_2(n),f_3(n)))$

$(b)$

$\text{3.}$

將輸入的$n$個數值進行編號並使其由小到大排列，以$1,4,2,8,5,7$為例，可以編號為$(0,1),(1,4),(2,2),(3,8),(4,5),(5,7)$四點，將其轉換成二維點後，尋找最近點對之距離，如果是等於$1$的話便表示有數字重複，反之則否。

$\text{4.}$

開另一個陣列$b[]$，將其中的數值皆設為零。然後歷遍原輸入陣列$a[]$，對於第$i$項，將$b_{a_i}$設為$1$代表該數字已經被用過了。如此，若遇到一個數字$a_k$，其數值在$b[]$對應到的$b_{a_k}$不為零時，可以確定該數字重複。

本作法時間複雜度為$O(n)$，額外空間需求$O(n)$，並且不會更改到原輸入陣列。